# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: quick_sort.py 
@time: 2019/7/1 15:03
"""
'''
快速排序须知：
又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。它是处理大数据最快的排序算法之一，它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。
'''
def quickSort(nums):
    # 这种写法的平均空间复杂度为0(nlogn)
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    # 基准值
    left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot]
    right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
    return quickSort(left) + [pivot] + quickSort(right)



# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
print(quickSort(nums))